package Leetcode.StackAndQueue.largestRectangleArea84;

import java.util.Stack;

/**
 * 单调栈解法
 * 时间复杂度O(n)
 * 空间复杂度O(n)
 * 空间换时间 最优解法
 *
 * 思路 暴力解法是固定中间的一根棒子 分别去找左边界和右边界
 * 边界是值第一个小于这根棒子长度的点 因为只要找到这个边界 即该棒子所决定的面积已经决定
 * 因为遇到小于这个棒子的点 所决定的面积不再由这个棒子决定 而是由小的决定
 * 对于暴力解法 每固定一根棒子 都要去找他的左边界和右边界  即第i根棒子所遍历的结果无法为i+1根棒子所需要的遍历提供帮助
 * 故用单调栈来解决这个问题
 * 2，1，5，6，2，3
 * 对于这个例子
 * 首先先往栈里添加一个0 作为哨兵 目的的后面不用再做栈非空的判断
 * 此时栈中为 0  对数组从1遍历
 * 先进行判断下标为1的值对应的高为2 要高于栈中下标为0对应的0 的值 将下标1入栈 此时无法判断高为2的右边界 即无法确定面积
 * 此时栈中为 0 1  开始遍历数组下标为2 的值
 * 此时下标2对应的高为1 小于栈顶下标为1 对应的高2  故此时高为2的右边界确定了 故面积确定 将下标1出栈 再进行判断
 * 发现下标2对应的1 要大于栈顶0对应的高0  不处理 继续寻找右边界 将下标2入栈
 * 算出高为2 的面积   此时栈中 0 2
 * 继续遍历 发现 5 大于 1 将5的下标3入栈 继续发现 6 的 大于栈顶下标对应的 5 将6的下标入栈
 * 栈中为 0 2 3 4
 * 遍历到2 的时候发现 2小于栈顶下标对应的6 故6作为高的右边界已经找到 计算出高为6面积的值 并将6的下标出栈
 * 栈中为 0  2 3  发现2小于栈顶下标对应的5 的值 故高为5的右边界已经找到 计算出面积 将5的下标出栈
 * 栈中为 0  2 此时2大于栈顶下标对应的1 将2的下标入栈
 * 栈 0 2 5   此时3大于栈顶下标对应的2  将3的下标入栈
 * 栈 0 2 5 6  继续遍历发现7对应的值为0 小于栈顶对应的3 将高为3的面积算出来出栈 再将3对应下标出栈
 * 以此将高为1 和 2 的出栈 后发现 7对应的值0 并不大于 0 对应的下标0 将0 入栈 此时循环结束
 * 栈也为空 此等头尾两哨兵的妙用在于此
 *
 */
public class Solution3 {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        int maxArea = 0;
        int[] newHeights = new int[len + 2];

        for(int i = 0; i < len; i++) {
            newHeights[i + 1] = heights[i];
        }
        heights = newHeights;
        len += 2;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for(int i = 1; i < len; i++) {
            while( heights[i] < heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea,h * width);
            }
            stack.push(i);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int nums[] = {2,1,5,6,2,3};
        Solution3 solution = new Solution3();
        System.out.println(solution.largestRectangleArea(nums));
    }
}
